package com.gaogzhen.algorithm.sort;

/**
 * 希尔排序
 */
public class Shell {

    // 排序
    public static void sort(Comparable[] a) {
        // 1、根据数组长度确定增长量h
        int len = a.length;
        int h = len / 2;
        Comparable tmp;
        // 2、排序
        while (h > 0) {
            for (int i = h; i < len; i++) {
                tmp = a[i];
                int preIndex = i - h;
                while (preIndex >= 0 && compare(a[preIndex], tmp)) {
                    a[preIndex + h] = a[preIndex];
                    preIndex -= h;
                }
                a[preIndex + h] = tmp;
            }
            h /= 2;
        }
    }

    // 比较a是否大于b
    public static boolean compare(Comparable a, Comparable b) {
        return a.compareTo(b) > 0;
    }

    // 交换元素
    public static void exch(Comparable[] a, int i, int j) {
        Comparable t = a[i];
        a[i] = a[j];
        a[j] = t;
    }
}
